package StringSecond.SwordOffer.StringSecond;

public class StrStr {
    /**
     * 实现 strStr()
     * 实现strStr()函数。
     * <p>
     * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
     * <p>
     *
     * <p>
     * 说明：
     * <p>
     * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     * <p>
     * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
     * <p>
     *
     * <p>
     * 示例 1：
     * <p>
     * 输入：haystack = "hello", needle = "ll"
     * 输出：2
     * 示例 2：
     * <p>
     * 输入：haystack = "aaaaa", needle = "bba"
     * 输出：-1
     * 示例 3：
     * <p>
     * 输入：haystack = "", needle = ""
     * 输出：0
     */
    //暴力法查找字符串
    public static int strStr(String haystack, String needle) {
        char[] chars = haystack.toCharArray();
        char[] chars1 = needle.toCharArray();

        int i = 0;
        int j = 0;
        while (i < chars.length && j < chars1.length) {
            if (chars[i] == chars1[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j == chars1.length) {
            return i - j;
        } else {
            return -1;
        }
    }
//    //kmp算法查找字符串
//    public static int strStr(String haystack, String needle) {
//        if (needle.length() == 0) return 0;
//        char[] S = haystack.toCharArray();
//        char[] T = needle.toCharArray();
//        int[] next = getNext(T);
//        int i = 0;
//        int j = 0;
//        while (i < S.length && j < T.length) {
//            if (j == -1 || S[i] == T[j]) {
//                i++;
//                j++;
//            } else {
//                j = next[j];
//            }
//        }
//        if (j == T.length) return i - j;
//        else return -1;
//    }
//
//    public static int[] getNext(char[] t) {
//        int[] next = new int[t.length];
//        next[0] = -1;
//        int i = 0;
//        int j = -1;
//        while (i < t.length - 1) {
//            if (j == -1 || t[i] == t[j]) {
//                i++;
//                j++;
//                next[i] = j;
//            } else {
//                j = next[j];
//            }
//        }
//        return next;
//    }

    public static void main(String[] args) {
        String haystack = "ACTGPACTGKACTGPACY";
        String needle = "ACTGPACY";
        System.out.println(strStr(haystack, needle));
    }
}
